package EveryDay;

public class P2187 {
    public static void main(String[] args) {
        P2187Test01 p2187Test01=new P2187Test01();
        int[] a={1,2,3};
        System.out.println(p2187Test01.minimumTime(a,5));
    }
}


/**
 * 二分答案
 * */
class P2187Test01{
    public long minimumTime(int[] time, int totalTrips) {
        //找到边界，减少计算量
        long minT=Long.MAX_VALUE;
        for(long t:time){
            minT=Math.min(t,minT);
        }

        long l=minT-1;
        long r=totalTrips*minT;
        //二分答案，最少时间就是答案
        long mid;
        long ans=-1;
        while(l<=r){
            mid=(l+r)/2;
            //如果车次大于total，那么说明时间过长，需要缩短时间
            if(find(time,totalTrips,mid)){
                r=mid-1;
                ans=mid;
            }
            //否则就是时间过短
            else{
                l=mid+1;
            }
        }
        return ans;
    }

    private boolean find(int[] time,int total,long mid){
        int num=0;
        int length=time.length;
        for (int j : time) {
            //计算车次
            num += mid / j;
            //如果大于直接返回，减少计算量
            if(num>=total)
                return true;
        }
       return false;
    }
}

class P2187Test02{
    public long minimumTime(int[] time, int totalTrips) {
        long minT = Long.MAX_VALUE;
        for (int t : time) {
            minT = Math.min(minT, t);
        }
        // 循环不变量：check(left) 恒为 false
        long left = minT - 1;
        // 循环不变量：check(right) 恒为 true
        long right = totalTrips * minT;
        // 开区间 (left, right) 不为空
        while (left + 1 < right) {
            long mid = (left + right) / 2;
            if (check(mid, time, totalTrips)) {
                // 缩小二分区间为 (left, mid)
                right = mid;
            } else {
                // 缩小二分区间为 (mid, right)
                left = mid;
            }
        }
        // 此时 left 等于 right-1
        // check(left-1) = false 且 check(right) = true，所以答案是 right
        return right;
    }

    private boolean check(long x, int[] time, int totalTrips) {
        long sum = 0;
        for (int t : time) {
            sum += x / t;
            if (sum >= totalTrips) {
                return true;
            }
        }
        return false;
    }
}